package com.netscenery.util;

public class Link<E> {
	public enum SortOrder{ASCEND,DESCEND,NATURAL;}
	private LinkNode header;
	private SortOrder sortOrder = SortOrder.NATURAL;
	private int size;
	
	public Link(SortOrder sortOrder){
		this();
		this.sortOrder = sortOrder;
	}
	public Link(){
		header = new LinkNode();
		header.setNext(null);
		size = 0;
	}

	
	/**
	 * @return the size
	 */
	public int size() {
		return size;
	}



	/**
	 * @return the header
	 */
	public LinkNode getHeader() {
		return header;
	}

	
	public boolean isEmpty(){
		if (null == header){
			return true;
		}
		if (null == header.getNext()){
			return true;
		}
		
		return false;
	}

	public boolean insert(  E data){
		if (null == data){
			return false;
		}
		
		LinkNode node = new LinkNode((ILinkData)data);
		return insert(node);
	}
	
	public boolean insert( E data,int index){
		if (null == data){
			return false;
		}
		if (this.sortOrder != SortOrder.NATURAL){
			return false;
		}
		LinkNode node = new LinkNode((ILinkData)data);
		return insert(node,index);
	}
	/**
	 * ��ָ����λ�ò���ڵ�
	 * @param node
	 * @param index
	 * @return
	 */
	private boolean insert(LinkNode node, int index){
		if (null == node){
			return false;
		}
		if (null == node.getData()){
			return false;
		}
		if (null == header){
			return false;
		}
		if (index < 0){
			return false;
		}
		//���sizeΪ0����ֱ�Ӳ���
		if (0 == size){
			return insert(node);
		}
		
		if (index >=size){
			return false;
		}
		

		LinkNode firstNode = header.getNext();
		if(null == firstNode){
			return false;
		}
		LinkNode curNode = firstNode;
		for(int i = 0; i < index;i++){
			curNode = curNode.getNext();
			if (null == curNode){
				return false;
			}
		}
		
		LinkNode preNode = curNode.getPre();
		if(null != preNode){
			preNode.setNext(node);
			node.setPre(preNode);
			node.setNext(curNode);
			curNode.setPre(node);
			size++;
		}
		else {
			header.setNext(node);
			node.setPre(null);
			node.setNext(firstNode);
			firstNode.setPre(node);
			size++;
		}
		
		
		return true;
		
	}
	private boolean insert(LinkNode node){
		if (null == node){
			return false;
		}
		if (null == node.getData()){
			return false;
		}
		if (null == header){
			return false;
		}
		

		if(isEmpty()){
			header.setNext(node);
			node.setNext(null);
			node.setPre(null);
			size++;
			return true;
		}
		
		LinkNode curNode = header.getNext();

		while(null != curNode){
			LinkNode preNode = curNode.getPre();
			LinkNode nextNode = curNode.getNext();
			
			ILinkData curData = curNode.getData();
			ILinkData insertData = node.getData();
			// 如果当前数据比待插入数据小
			if (curData.compare(insertData) < 0) {
				// 如果是降序排列的话，需要插在本节点之前
				if (this.sortOrder == SortOrder.DESCEND) {

					if (null == preNode) {
						// 如果比第一个节点大，则插入到第一个节点前
						header.setNext(node);
						node.setPre(null);
					} else {
						node.setPre(preNode);
						preNode.setNext(node);
					}

					node.setNext(curNode);
					curNode.setPre(node);
					size++;
					return true;
				}

			}
			// 如果当前数据比插入数据大
			else {
				// 如果是升序排列的话，则插入到当前节点之前
				if (this.sortOrder == SortOrder.ASCEND) {
					if (null == preNode) {
						// 如果比第一个节点小，则插入到第一个节点之前
						header.setNext(node);
						node.setPre(null);
					} else {
						preNode.setNext(node);
						node.setPre(preNode);
					}

					node.setNext(curNode);
					curNode.setPre(node);
					size++;
					return true;
				}
			}
			//����β
			if (null == nextNode){
				curNode.setNext(node);
				node.setPre(curNode);
				node.setNext(null);
				size++;
				return true;
			}
			
			curNode = curNode.getNext();
		}
		
		return false;
		
	}
	private LinkNode getNode(int index){
		if (null == header){
			return null;
		}
		
		if (index >= size){
			return null;
		}
		LinkNode firstNode = header.getNext();
		if(null == firstNode){
			return null;
		}
		LinkNode curNode = firstNode;
		for(int i = 0; i < index;i++){
			curNode = curNode.getNext();
			if (null == curNode){
				return null;
			}
		}
		return curNode;
	}
	
	
	@SuppressWarnings("unchecked")
	public E get(int index){
		LinkNode node = getNode(index);
		if (null == node){
			return null;
		}
		
		return ((E)(node.getData()));
	}

	@SuppressWarnings("unchecked")
	public E getNext(int index){
		LinkNode curNode = getNode(index);
		if (null == curNode){
			return null;
		}
		curNode = curNode.getNext();
		if (null == curNode){
			return null;
		}
		
		return ((E)(curNode.getData()));
	}
	public boolean contains(E data){
		if (null == data){
			return false;
		}
		
		if (null == header){
			return false;
		}
		
		if (null == header.getNext()){
			return false;
		}
		
		LinkNode curNode = header.getNext();
		while(null != curNode){
			if (curNode.getData().equals(data)){
				return true;
			}
			curNode = curNode.getNext();
		}
		
		return false;
	}
	/**
	 * ��ȡָ������������е�λ��
	 * @param data
	 * @return
	 */
	public int getIndex(E data){
		if (null == data){
			return -1;
		}
		
		if (null == header){
			return -1;
		}
		
		if (null == header.getNext()){
			return -1;
		}
		
		LinkNode curNode = header.getNext();
		int index = 0;
		while(null != curNode){
			if (curNode.getData().equals(data)){
				return index;
			}
			curNode = curNode.getNext();
			index++;
		}
				
		return -1;
	}
	
	public LinkNode remove(E data){
		if (null == data){
			return null;
		}
		
		if (null == header){
			return null;
		}
		
		if (null == header.getNext()){
			return null;
		}
		
		LinkNode curNode = header.getNext();
		while(null != curNode){
			if (curNode.getData().equals(data)){
				LinkNode preNode = curNode.getPre();
				LinkNode nextNode = curNode.getNext();
				if (null == preNode){
					//��һ���ڵ�
					header.setNext(nextNode);
					
				}
				else {
					preNode.setNext(nextNode);
				}
				
				if (null != nextNode){
					nextNode.setPre(preNode);
				}
				size--;
				return curNode;
				
			}
			curNode = curNode.getNext();
			
		}
		
		return null;
	}
	
	@SuppressWarnings("unchecked")
	public E remove(int index){
		if (null == header){
			return null;
		}
		
		if (index >= size){
			return null;
		}
		LinkNode firstNode = header.getNext();
		if(null == firstNode){
			return null;
		}
		LinkNode curNode = firstNode;
		for(int i = 0; i < index;i++){
			curNode = curNode.getNext();
			if (null == curNode){
				return null;
			}
		}
		LinkNode preNode = curNode.getPre();
		LinkNode nextNode = curNode.getNext();
		
		if (null == preNode){
			//��һ���ڵ�
			header.setNext(nextNode);
			
		}
		else {
			preNode.setNext(nextNode);
		}
		
		if (null != nextNode){
			nextNode.setPre(preNode);
		}
		size--;
		return ((E)(curNode.getData()));
	}
	/**
	 * ��Դ�ڵ��ƶ���Ŀǰ�ڵ�֮�����Ŀ�Ľڵ�Ϊ�գ����ƶ���������ײ���Ϊ��һ���ڵ�
	 * @param src
	 * @param dst
	 * @return
	 */
	public boolean move(E src, E dst){
		if (null == src){
			return false;
		}
		//Դ��Ŀ����ͬ������Ҫ�ƶ�
		if (src == dst){
			return true;
		}
		//���Ƴ�Դ�ڵ�
		remove(src);
		if(null == dst){
			return insert(src, 0);
		}
		
		int index = getIndex(dst);
		if (-1 == index){
			return false;
		}
		if (index + 1 == size){
			return insert(src);
		}
		else {
			return insert(src, index + 1);
		}
			
	}
	
	/**
	 * ��ָ��index�Ľڵ��ƶ���ָ��index��Ŀ�Ľڵ�֮��
	 * @param src
	 * @param dst
	 * @return
	 */
	public boolean move(int srcIndex, int dstIndex){
		
		//Դ��Ŀ����ͬ������Ҫ�ƶ�
		if (srcIndex == dstIndex){
			return true;
		}
		//���Ƴ�Դ�ڵ�
		E srcData = remove(srcIndex);
		
		if (srcIndex < dstIndex){
			if (dstIndex == size){
				return insert(srcData);
			}
			return insert(srcData,dstIndex);
		}
		
		return insert(srcData, dstIndex + 1);
			
	}
}
